package com.leetcode.algorithm.y22.m08.w1;

/**
 * 695. 岛屿的最大面积
 * 
 * https://leetcode.cn/problems/max-area-of-island/
 * 
 * @author jie.deng
 *
 */
class Question0695Solution02 {

	public int maxAreaOfIsland(int[][] grid) {
		int rows = grid.length;
		int cols = grid[0].length;
		boolean existsIsland = false;
		UnionFind uf = new UnionFind(rows * cols);
		for (int row = 0; row < rows; row++) {
			for (int col = 0; col < cols; col++) {
				int curIdx = row * cols + col;
				if (grid[row][col] == 1) {
					existsIsland = true;
					for (int[] dir : new int[][] { { 0, -1 }, { -1, 0 } }) {
						// 左和上
						int r = row + dir[0];
						int c = col + dir[1];
						if (r >= 0 && r < rows && c >= 0 && c < cols) {
							if (grid[r][c] == 1) {
								int idx = r * cols + c;
								uf.union(curIdx, idx);
							}
						}
					}
				}
			}
		}
		return existsIsland ? uf.maxSize : 0;
	}
	
	class UnionFind {
		// 实际存储的是parent
		int roots[];
		int sizes[];
		int maxSize;

		public UnionFind(int size) {
			roots = new int[size];
			sizes = new int[size];
			for (int i = 0; i < size; i++) {
				roots[i] = i;
				sizes[i] = 1;
			}
			maxSize = 1;
		}

		private int findRoot(int x) {
			if (x == roots[x]) {
				return x;
			}
			// 路径压缩
			return x = findRoot(roots[x]);
		}

		public void union(int x, int y) {
			int rootX = findRoot(x);
			int rootY = findRoot(y);
			if (rootX != rootY) {
				if (sizes[rootX] >= sizes[rootY]) {
					roots[rootY] = rootX;
					sizes[rootX] += sizes[rootY];
					if (sizes[rootX] > maxSize) {
						maxSize = sizes[rootX];
					}
				} else {
					roots[rootX] = rootY;
					sizes[rootY] += sizes[rootX];
					if (sizes[rootY] > maxSize) {
						maxSize = sizes[rootY];
					}
				}
			}
		};

	}	
}